@make(PublicationOrderForm,Number 15,AnnouncementDate "January 1982")
@begin(center)
List Number 15
@end(center)
@Entry(Code "STAN-CS-81-882",
	Title "Fast Matrix Multiplication Without APP Algorithms",
	Author "V. Pan",
	Price "$2.95", FREE,
	Note "30 pages",
	Date "October 1981")

The method of trilinear aggregating with implicit canceling for the design
of fast matrix multiplication (MM)  algorithms is revised and is  formally
presented with the use of Generating Tables and of linear  transformations
of the problem of MM. It is shown  how to derive the exponent of MM  below
2.67 even without the use of approximation algorithms.

@Entry(Code "STAN-CS-81-883",
	Title "On Program Transformations for Abstract Data Types and Concurrency",
	Author "P. Pepper",
	Price "$3.15", FREE,
	Note "37 pages",
	Date "October 1981")

We study  transformation rules  for a  particular class  of abstract  data
types, namely types that are representable by recursive mode declarations.
The transformations  are tailored  to the  development of  efficient  tree
traversal and they allow for concurrency.  The techniques are  exemplified
by an implementation of concurrent insertion and deletion in 2-3-trees.


@Entry(Code "STAN-CS-81-884",
	Title "Optimal Design of Distributed Databases",
	Author "Stefano Ceri, Shamkant Navathe, Gio Wiederhold",
	Price "$3.45", FREE,
	Note "48 pages",
	Date "December 1981")

The optimal distribution of a database, given information on the data  and
their usage, among sites in a distributed computer network is determined.

The required information consists specifically of
a)  A global conceptual database schema for the enterprise,
b)  A tabulation of (important) transactions and their volume and source sites,
c)  Distribution constraints.

The objects to be distributed may be files or fragments of files and  have
as attributes cardinality and tuple  size.  The schema specified  includes
links onto which the joins of the transactions are specified.

Tuples are the  primitives transmitted  when required  over links  between
remote sites.  The transmission cost is independent of distance.

Transactions are  specified in  terms of  entry points  and objects.   The
model  is  optimized  in  terms  of  total  transaction  processing  cost.
Solutions to the model are given for  a number of cases and were found  to
be both interesting and reasonable.

A section of the  paper deals with the  effects of partial replication  of
objects on multiple sites.  Here some  heuristics are defined in order  to
arrive at a solution.

An indication of further issues to be addressed is included.


@Entry(Code "STAN-CS-81-885",
	Title "The EMYCIN Manual",
	Author "W. VanMelle, A.C. Scott, J.S. Bennett, M. Peairs",
	Price "$6.30", FREE,
	Note "143 pages",
	Date "October 1981")

This manual describes  a domain-independent system,  called EMYCIN,  for
constructing  one  class   of  expert   computer  programs:   rule-based
consultants.  The resulting programs use knowledge specific to a problem
domain to provide consultative advice to a client.  The  system-building
tool, EMYCIN,  is based  on  the domain-independent  core of  the  MYCIN
program.  Domain knowledge is represented in EMYCIN systems primarily as
production rules, which are applied by a goal-directed backward-chaining
control structure.   Rules and  consultation  data may  have  associated
measures of certainty, and incomplete data entry is allowed.  The system
includes an explanation facility that can display the line of  reasoning
followed by  the consultation  program, and  answer questions  from  the
client about the contents of its knowledge base.

To aid the system  designer in producing a  knowledge base for a  domain
quickly and accurately,  EMYCIN provides the  following features: (1)  a
terse, stylized, but easily understood  language for writing rules;  (2)
extensive checks to catch common user errors, such as misspellings;  and
(3) methods  for  handling  all  necessary  bookkeeping  chores.   Other
human-engineering features allow the system architect to produce, with a
minimum of effort, a consultation program that is pleasing in appearance
to the client.

Several  consultation  programs  have   been  developed  using   EMYCIN,
including  consultants  for  medical  problems  and  a  consultant   for
structural analysis.


@Entry(Code "STAN-CS-81-886",
	Title "The Concept of a Meta-Font",
	Author "Donald E. Knuth",
	Price "$2.35", FREE,
	Note "12 pages",
	Date "October 1981")

A single drawing of a single letter reveals only a small part of what  was
in the  designer's mind  when  that letter  was  drawn. But  when  precise
instructions are given about how to make such a drawing, the  intelligence
of that letter  can be  captured in  a way that  permits us  to obtain  an
infinite variety of related letters  from the same specification.  Instead
of merely describing a single  letter, such instructions explain how  that
letter would change  its shape if  other param\-eters of  the design  were
changed. Thus an entire font of letters and other symbols can be specified
so  that  each  character  adapts  itself  to  varying  conditions  in  an
appropriate way.  Initial  experiments with  a  precise language  for  pen
motions suggest strongly that the font  designer of the future should  not
simply design isolated alphabets; the challenge will be to explain exactly
how each design should adapt itself gracefully to a wide range of  changes
in the  specification.  This  paper  gives examples  of  a  meta-font  and
explains the changeable parameters in its design.


@Entry(Code "STAN-CS-81-887",
	Title "Finding the Convex Hull of Simple Polygon",
	Author "Ronald Graham, Frances Yao",
	Price "$2.25", FREE,
	Note "9 pages",
	Date "November 1981")

It is well known that the convex hull of a set of n points in the (Euclidean)
plane can be found by an algorithm having worst-case complexity O(n log n).
In this note we give a short linear algorithm for finding the convex hull
in the case that the (ordered) set of points from the vertices of a simple
(i.e., non-self-intersecting) polygon.


@Entry(Code "STAN-CS-81-888",
	Title "Numerical Solution of Transport Equations",
	Author "William D. Gropp",
	Price "not available", FREE,
	Note "108 pages",
	Date "December 1981")

In this dissertation we discuss the numerical solution of systems of hyperbolic
partial differential equations with lower order terms and step function initial
data.  These equations arise in modeling the propagation of a signal with loss,
such as a signal in a resistive co-axial cable, or the flow of neutrons in a
reactor.  Majda and Osher have shown that dissipative finite difference
approximations to such problems display a numerical artifact which is not
encountered for scalar equations.  Namely, noise from an initial discontinuity 
propagates into a large region behind the discontinuity.  Their results do not
apply in the vicinity of a discontinuity, and our goal is to discover the
detailed behavior in this region.  This information will be of use in 
constructing algorithms that attempt to accurately approximate
solutions with discontinuities or shocks.

@Entry(Code "STAN-CS-81-889",
	Title "AL Users Manual",
	Author "Shahid Mujtaba, Ron Goldman",
	Price "$7.05", not available,
	Note "168 pages",
	Date "December 1981")

AL is a high-level programming language for manipulator control useful  in
industrial assembly research.  This  document describes the current  state
of the AL system now in operation at the Stanford Artificial  Intelligence
Laboratory, and teaches the reader how to use it.  The system consists  of
the AL  compiler  and runtime  system  and the  source  code  interpreter,
POINTY,  which  facilitates  specifying   representation  of  parts,   and
interactive execution of AL statements.


@Entry(Code "STAN-CS-81-890",
	Title  "Boundary Conditions for Hyperbolic Systems of Partial
		Differential Equations Having Multiple Time Scales",
	Author  "Robert L. Higdon",
	Price  "not available", FREE,
	Note  "136 pages",
	Date  "August 1981")

This paper is concerned with linear hyperbolic systems of partial 
differential equations for which certain of the associated
propagation speeds are a great deal larger than the other propagation aspeeds.
In certain cases the fast modes allowed by such a system are not present in the true
physical solution.  Yet the fact that such modes are allowed means that
when one tries to compute a numerical solution to an initial-bourdary
value problem, the errors generated can propagate quite rapidly.  In
particular, when the boundary data used for the computation are less
accurate than the initial data, the fast modes can cause a rapid 
contamination of the calculation in the interior.  The situation described here
is often encountered when equations of gas dynamics are used to
model the bahvior of the earth's atmosphere.  To prevent this loss
of accuracy, one would like to have boundary conditions which prevent
fast waves from entering the region.  The goal of this paper is to find such
conditions.

In order to do this, we first transform the given system to an approximate
diagonal form in such a way that each of the new
dependent variables can be identified as a slow, incoming
fast, or outgoing fast component of the solution.  We then find 
local boundary conditions which supress the incoming fast part.  
Pseudo-differential operators are used throughout the entire process.  The
effects of these boundary conditions are analyzed using methods
from the theory of propagation of singularities for linear partial
differential equations.  Boundary conditions have been developed for a model
problem in one space dimension and for the linearized shallow water equations. 
We have included the results of some numerical calculations which demonstrate
the effectiveness of these conditions.

@Entry(Code "STAN-CS-81-891",
	Title "The Role of the Critic in Learning Systems",
	Author "T.G. Dietterich, B. G. Buchanan",
	Price  "$2.70", FREE,
	Note  "23 pages",
	Date  "December  1981")


Buchanan, Mitchell, Smith and Johnson [Buchanan 78a] described a general model
of learning systems that included a component called the Critic.  The task  of
the Critic was described as threefold:  evaluation of the past actions of  the
performance element of the learning  system, localization of credit and  blame
to particular portions of that performance element, and @i(recommendation)  of
possible improvements  and modifications  in  the performance  element.   This
article analyzes these three tasks in detail and surveys the methods that have
been employed in existing learning systems to accomplish them.  The  principle
method used  to  evaluate the  performance  element  is to  develop  a  global
performance standard by (a)  consulting an external  source of knowledge,  (b)
consulting an  internal  source of  knowledge,  or (c)  conducting  controlled
experiments  on   the   performance  element.    Recommendations   have   been
communicated to the learning element  using (a) local training instances,  (b)
correlation coefficients, and (c) partially-instantiated schemata.

@Entry(Code "STAN-CS-82-892",
	Title "An Algorithm for Reducing Acyclis Hypergraphs",
	Author "Gabriel M. Kuper",
	Price "$2.25", FREE,
	Note "9 pages",
	Date "January 1982")

The following is a description of an algorithm to compute 
efficiently
the Graham reduction
of an acyclic hypergraph with sacred nodes. To apply the algorithm 
we must already have a tree representation of the hypergraphs, and therefore
it is useful  
when we have a fixed hypergraph and wish to compute Graham reductions many times,
as we do in the System/U query interpretation algorithm.

@Entry(Code "STAN-CS-82-893",
	Title "A Compiler Generator for Semantic Grammars",
	Author "Lawrence Paulson",
	Price "$7.00", not available,
	Note "166 pages",
	Date "December 1981")

Most programming languages are defined using English,
with its attendant ambiguities.
This thesis introduces the semantic grammar, a formal, unambiguous 
notation for syntax and semantics.
Semantic grammars evolved from denotational semantics and
attribute grammars.
Appendix D is a grammar that expresses the syntax,
static semantics, and dynamic semantics of Pascal.

The thesis describes a compiler generator that automatically
translates semantic grammars into compilers.
It has generated Pascal and Fortran compilers,
and run numerous programs, including an LR(0) parser constructor.
The compilers are much slower than hand-written ones,
but are efficient enough to run test programs for 
experimental languages.
The compiler generator
consists of a grammar analyzer, a table-driven universal translator, 
and an SECD stack machine.

@newpage
@Entry (Code "STAN-CA-82-894",
	Title "Methodology for Building an Intelligent Tutoring System",
	Author "William J. Clancey",
	Price "$3.65", FREE,
	Note "55 pages",
	Date "October 1981")

Over the past 5 years we have been developing a computer program to teach
medical diagnosis.  Our research synthesizes and extends results in
artificial intelligence (AI), medicine, and cognitive psychology.  This
paper describes the progression of the research, and explains how theories
from these fields are combined in a computational model.  The general
problem has been to develop an "intelligent tutoring system" by adapting
the MYCIN "expert system."  This conversion requires a deeper understanding of the 
nature of expertise and explanation than originally required for developing
MYCIN, and a concomitant shift in perspective from simple
performance goals to attaining psychological validity in the program's
reasoning process.

Others have written extensively about the relation of artificial intelligence
to cognitive science (e.g., Pylyshyn, Boden).  Our purpose here is not to repeat
those arguments, but to present a case study which will provide a common point
for further discussion.  To this end, to help evaluate the state of 
cognitive science, we will outline our methodology and survey what resources
and viewpoints have helped our research.  We will also discuss pitfalls
that other AI-oriented cognitive scientists may encounter.  Finally, we
will present some questions coming out of our work which might suggest
possible collaboration with other fields of research.

@Entry (Code "STAN-CS-82-895",
	Title "GLISP Users Manual",
	Author "Gordon S. Novak, Jr.",
	Price "$3.15", FREE,
	Note "38 pages",
	Date "January 1982")

GLISP is a high-level, LISP-based language which is compiled into
LISP.  GLISP provides a powerful abstract datatype facility, allowing
description and use of both LISP objects and objects in A.I.
representation languages.  GLISP language features include PASCAL-like
control structures, infix expressions with operators which facilitate
list manipulation, and reference to objects in PASCAL-like or
English-like syntax.  English-like definite reference to features of
objects which are in the current computational context is allowed;
definite references are understood and compiled
relative to a knowledge base of object descriptions.
Object-centered programming is supported; GLISP can substantially
improve runtime performance of object-centered programs by optimized
compilation of references to objects.  This manual describes the GLISP
language and use of GLISP within INTERLISP.


@Entry (Code "STAN-CS-82-896",
	Title "The Epistemology of a Rule-Based Expert System: A framework for
		Explanation",
	Author "William J. Clancey",
	Price "$3.85", FREE,
	Note "61 pages",
	Date "November 1981")

Production rules are a popular representation for encoding heuristic knowledge
in programs for scientific and medical problem solving.  However,
experience with one of these programs, MYCIN, indicates that the representation
has serious limitations: people other than the original rule authors find it 
difficult to modify the rule set, and the rules are unsuitable for use in other 
settings, such as for application to teaching.  These problems are rooted
in fundamental limitations in MYCIN's original rule representation:
the view that expert knowledge can be encoded as a uniform, weakly-structured
set of if/then associations is found to be wanting.

To illustrate these problems, this paper examines MYCIN's rules from the 
perspective of a teacher trying to justify them and to convey a problem-solving
approach.  We discover that individual rules play different rules, have 
different kinds of justifications, and are constructed using
different rationales for the ordering and choice of premise clauses.  This
design knowledge, consisting of structural and strategic concepts which
lie outside the representation, is shown to be procedurally embedded in
the rules.  Moreover, because the data/hypothesis associations are themselves a 
proceduralized form of underlying disease models, they can only be
supported by appealing to this deeper level of knowledge.  Making
explicit this structural, strategic and support knowledge enhances the ability
to understand and modify the system.

@blankspace(1 inch)
@b(ERRATA)
STAN-CS-81-877, Zohar Manna, @i(Verification of Sequential Programs:
Temporal Axiomatization).
Replace line 6 in the proof of NP (page 15) by the following lines:
@blankspace(2 inch)